package 力扣日常刷题.木22一月.第06天0114;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/14
 * @description
 */
public class Demo08回溯中等复原IP地址 {

    ArrayList<String> ans = new ArrayList<>();
    char[] chars;

    public List<String> restoreIpAddresses(String s) {
        chars = s.toCharArray();
        if (s.length() >= 4) {
            dfs(0, new String(), 0);
        }
        return ans;
    }

    void dfs(int index, String s, int seq) {
        if (seq == 4 && index == chars.length) {
            ans.add(s.substring(0, s.length() - 1));
            return;
        }
        if (seq == 4 || index == chars.length) return;

        int curSum = 0;

        for (int i = index; i < chars.length; i++) {
            curSum += chars[i] - '0';

            if (i - index >= 1 && chars[index] - '0' == 0) break;
            if (curSum > 255) break;
            dfs(i + 1, s + curSum + ".", seq + 1);
            curSum *= 10;
        }
    }
}
